package com.algorithm.liyc.echa;

import com.algorithm.liyc.entity.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 111.二叉树的最小深度
 * 给定一个二叉树，找出其最小深度。
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 * 说明: 叶子节点是指没有子节点的节点。
 *
 * 本题依然是前序遍历和后序遍历都可以，前序求的是深度，后序求的是高度。
 * ● 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
 * ● 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数后者节点数（取决于高度从0开始还是从1开始）
 * 那么使用后序遍历，其实求的是根节点到叶子节点的最小距离，就是求高度的过程，不过这个最小距离 也同样是最小深度。
 * @author Liyc
 * @date 2024/1/5 15:26
 **/

public class Solution8 {
    /**
     * 递归法，相比求MaxDepth要复杂点
     * 因为最小深度是从根节点到最近**叶子节点**的最短路径上的节点数量
     * @param root
     * @return
     */
    public int minDepth1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftMax = minDepth1(root.left);
        int rightMax = minDepth1(root.right);
        if (root.left == null) {
            return rightMax + 1;
        }
        if (root.right == null) {
            return leftMax + 1;
        }
        // 左右结点都不为null
        return Math.min(leftMax, rightMax) + 1;
    }

    /**
     * 迭代法-层序遍历
     * @param root
     * @return
     */
    public int minDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int minDepth = 0;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            minDepth++;
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = deque.poll();
                // 是叶子结点，直接返回depth，因为从上往下遍历，所以该值就是最小值
                if (treeNode.left == null && treeNode.right == null) {
                    return minDepth;
                }
                if (treeNode.left != null) {
                    deque.offer(treeNode.left);
                }
                if (treeNode.right != null) {
                    deque.offer(treeNode.right);
                }
            }
        }
        return minDepth;
    }
}
